package class8;

import common.TreeNode;
import common.TreeNodeUtils;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断二叉树是否为完全二叉树
 * 思路：
 * 1.二叉树的层级遍历
 * 2.只有有孩子没有左孩子，为非完全二叉树
 * 3.当遇到第一个左右不全时，下面的节点都是叶子节点
 */
public class Code05_isCBT {
    public static void main(String[] args) {
        TreeNode treeNode = TreeNodeUtils.getCBT();
        isCBT(treeNode);
    }

    public static boolean isCBT(TreeNode treeNode) {
        if (treeNode == null) return false;

        boolean leaf = false;
        TreeNode cur = treeNode;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(cur);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            TreeNode l = poll.left;
            TreeNode r = poll.right;
            // 1.如果左子节点为空而右子节点不为空，返回 false。这是因为完全二叉树的规则要求左子树必须先填充。
            // 2.如果已经遇到了叶子节点（leaf == true），而当前节点有左或右子树，则返回 false。
            // 这是因为完全二叉树的规则要求在遇到第一个叶子节点之后，后续的节点都必须是叶子节点，且没有左右子树。
            if ((l == null && r != null) ||
                    (leaf && (l != null || r != null))) {
                return false;
            }
            if (l != null) {
                queue.add(l);
            }
            if (r != null) {
                queue.add(r);
            }
            // 如果当前节点是叶子节点（即其左子节点或右子节点为 null），则标记 leaf 为 true，表示后续只能遇到叶子节点。
            if (l == null || r == null) {
                leaf = true;
            }

        }
        return true;
    }
}
